

\subsection{De-randomization Component}





%and using
%the \texttt{Reorder\_Fields} routine described in Algorithm 2.

%We implement the ``pointer un-randomization" by inserting the checking routine before
%the gimple statement, it changes the instance key to zero and uses
%the ``Reorder\_fields" described in Algorithm 2.



%For the second kind of pointers, the pointer points to a specific
%field of certain data structure instance. As the field may be
%randomized, the pointer will lead to an inconsistency.

%There are a number of practical issues which prevent the
%randomization to some data structures, for example, data structures
%involved in pointer operation (as static points-to analysis is
%difficult), data structures involved in pure assembly code (note gcc
%does allow the mixing of C code and assembly code), and data
%structures involved in external communications. As such, we have to
%implement to de-randomize the layout for those data structures to
%ensure the consistency and accuracy of the program.
%There are two \emph{de-randomization points}.


\vspace{0.1in} \noindent \textbf{De-randomizing Pointer Involved
Data Structures.} %There are two kinds of pointers: one points to the
%starting address of the data structure instance, the other points to
%the specific field of a data structure instance.
One of the \emph{de-randomization points} is type casting: if the
memory layout for an instance is randomized, the pointer, which
accesses the memory based on the data structure definition, will
lead to failure. For example, in Linux kernel, many kernel data
structure instances will be converted to \texttt{void} pointer in
hardware driver module due to unified interface. If the data
structure instance is randomized, the \texttt{void} pointer will
access the buffer inconsistently. Another example is the
\texttt{\_\_asm\_\_} statement. Data structure instance may be
transferred as the argument of an \texttt{\_\_asm\_\_} expression.
The assembly code in \texttt{\_\_asm\_\_} will access the data
structure instance based on the definition of the data structure
(this is how programmers develop software), and it will lead to the
inconsistency as well. To solve these issues, whenever we encounter
an assignment, we check whether the operands have the different
types and at least one of them is struct type, or a function call
statement with a pointer operand, we check whether the argument has
the different type from the parameter and at least one of them is
struct type. If so, we check whether the data structure instance is
randomized (the seed of the instance is positive). If so, we restore
the instance to its original memory layout. Otherwise, it indicates
the instance has not been randomized,  and mark the randomization
seed with a specific value (-1) which indicates this instance is
un-randomizable.

However, there are two exceptions in practice. One is the return
value for \texttt{malloc} family functions. At gimple level, these
functions will introduce a temporary variable with the \texttt{void}
pointer type which assigns the address to the pointer variable with
the data structure type.  The other case is the data structure
pointer initialized to NULL. In the gimple representation, NULL will
be indicated as an integer pointer type. We will give up the data
structure de-randomization for these two cases.




\vspace{0.1in} \noindent \textbf{De-randomizing External \& Shared
API Involved Data Structures.} % Since SALADS is able to randomize the
%layout for all of the data structures.
If a program is always self-contained, that is, all the code is
compiled from its source code without linking to any external code.
SALADS will work for all the data structures. However, rare programs
are self-contained, and most of them utilize standard library (e.g.,
\texttt{GNU LIBC}) or other interfaces such as system calls (POSIX
interfaces). On the other hand, if a compiled program provides the
interfaces (e.g., system call, hypercall) to other programs, or the
program itself is a shared library (e.g., when compiling \texttt{GNU
LIBC}), it will lead to the inconsistency when other programs use
the interfaces.

Fortunately, we could easily de-randomize a data structure instance
by simply changing its seed to -1 and reordering the fields of the
data structure instance. Thus, for the first case, SALADS examines
every function call, if it is an external function and a data
structure instance is passed as an argument or a return value of
these external functions, SALADS de-randomizes these instances. For
the second case, we need the priori knowledge of the program, in
particular which function in this program will be used by other
programs. For example, for Linux kernel, SALADS will de-randomize
the data structure instances used in system calls.



%\subsection{Other Practical Issues}
%Besides the de-randomization problem, we also encountered some other
%issues. In particular, as each data structure instance in SALADS has
%a seed, if multiple threads access the same data structure instance,
%it could lead a synchronization problem. As such, for user level
%program, we use the GNU library function
%\texttt{pthread\_mutex\_lock}, \texttt{pthread\_mutex\_unlock} to
%ensure a mutex access of each data structure instance, and for
%kernel level software, we use the spinlock interface
%\texttt{spin\_lock} and \texttt{spin\_unlock}. The other issue is a
%program may set a written protection attribute for the page that
%contains the data structure instances. For these programs, we will
%change the page attributes correspondingly before updating the
%instance layout.


% we use the cr0 to
%change the page attribute when we need to randomize the data
%structure instance.
%
%
%To solve the second problem, we use the cr0 to
%change the page attribute when we need to randomize the data
%structure instance.
%
%
%
%
%There are two other problems we encountered. The first one is synchronization problem, the second one
%is memory written protection. The first problem is due to the
%program may be multi-thread or SMP (Symmetrical Multi-Processing),
%and our inserted gimple statement will access the shared key
%mapping. The second problem is because the program may set the
%written protection attribute for the page that contains the data
%structure instances. To solve the first problem, we use the GNU
%library function \texttt{pthread\_mutex\_lock},
%\texttt{pthread\_mutex\_unlock} in user level applications. For
%linux kernel, we use the kernel spinlock interface ``spin\_lock" and
%``spin\_unlock". To solve the second problem, we use the cr0 to
%change the page attribute when we need to randomize the data
%structure instance.
